{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:28:56.525320Z",
     "start_time": "2018-12-20T11:28:55.427280Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Authorization for Minor Form.rtf\n",
      "child_wishlist_v2.csv\n",
      "gift_goodkids_v2.csv\n",
      "sample_submission_random_v2.csv\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "import math\n",
    "from collections import Counter\n",
    "from subprocess import check_output\n",
    "#看看文件是否存在，并且是不是用utf8\n",
    "print(check_output([\"ls\", \"input\"]).decode(\"utf8\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:29:19.879507Z",
     "start_time": "2018-12-20T11:29:00.102897Z"
    }
   },
   "outputs": [],
   "source": [
    "#居然转换成了ndarry\n",
    "#孩子喜欢的礼物\n",
    "gift_pref = pd.read_csv('input/child_wishlist_v2.csv',header=None).drop(0, 1).values\n",
    "#礼物喜欢的孩子\n",
    "child_pref = pd.read_csv('input/gift_goodkids_v2.csv',header=None).drop(0, 1).values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T12:59:24.803487Z",
     "start_time": "2018-12-13T12:59:01.036617Z"
    }
   },
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:29:36.485367Z",
     "start_time": "2018-12-20T11:29:36.478169Z"
    }
   },
   "outputs": [],
   "source": [
    "#有1000000个children\n",
    "n_children = 1000000 \n",
    "#1000种gift\n",
    "n_gift_type = 1000\n",
    "#每种gift1000个\n",
    "n_gift_quantity = 1000 \n",
    "#每个孩子有喜欢的100个礼物。(孩子开心)\n",
    "n_gift_pref = 100 # number of gifts a child ranks\n",
    "#每个礼物优先考虑1000个好孩子（圣诞老人开心）\n",
    "n_child_pref = 1000 # number of children a gift ranks\n",
    "#0-5000为三胞胎，triplets=50001 0.5%\n",
    "triplets = math.ceil(0.005 * n_children / 3.) * 3    \n",
    "#5001-45000双胞胎，即45000-5001+1=40000\n",
    "twins = math.ceil(0.04 * n_children / 2.) * 2    \n",
    "#根据目标函数里面定义的\n",
    "ratio_gift_happiness = 2\n",
    "ratio_child_happiness = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:29:39.851111Z",
     "start_time": "2018-12-20T11:29:39.845327Z"
    }
   },
   "outputs": [],
   "source": [
    "def index_of(in_list,val):\n",
    "    try:\n",
    "        return in_list.index(val)\n",
    "    except ValueError:\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 改写举例说明，以三胞胎为例\n",
    "<mark>改写的代码：</mark>\n",
    "```python\n",
    "def Triplet_Hij(prefer1, prefer2, prefer3):\n",
    "    res=[[],[],[]]\n",
    "    for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):        \n",
    "        score = 0\n",
    "        #对于三胞胎中的第一个人，偏爱有各种礼物的得分\n",
    "        if p in list(prefer1):\n",
    "            score += 2*(100 - list(prefer1).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        #对于三胞胎中的第二个人\n",
    "        if p in list(prefer2):\n",
    "            score += 2*(100 - list(prefer2).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        #对于三胞胎中的第三个人\n",
    "        if p in list(prefer3):\n",
    "            score += 2*(100 - list(prefer3).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        res[0].append(p)\n",
    "        res[1].append(2*score)\n",
    "        res[2].append(-6)\n",
    "    return res\n",
    "```\n",
    "```python\n",
    "Children1=[]\n",
    "for i in range(0, 6, 3):\n",
    "    res_triplet=Triplet_Hij(gift_pref[i], gift_pref[i+1], gift_pref[i+2])\n",
    "    Children1.append(res_triplet)\n",
    "    Children1.append(res_triplet)\n",
    "    Children1.append(res_triplet)\n",
    "```\n",
    "<mark>原代码：</mark>\n",
    "```python\n",
    "#三胞胎\n",
    "class Child_triplet(object):\n",
    "    def __init__(self, idx, prefer1, prefer2, prefer3):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        #三胞胎三个人，有三组不同的喜欢的礼物，所以对于三胞胎set(list(prefer1) + list(prefer2) + list(prefer3))肯定大于100\n",
    "        for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):\n",
    "            score = 0\n",
    "            #对于三胞胎中的第一个人，偏爱有各种礼物的得分\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第二个人\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第三个人\n",
    "            if p in list(prefer3):\n",
    "                score += 2*(100 - list(prefer3).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #这个是在干啥？\n",
    "            self.prefer_dict[p] = [2*score, -6]\n",
    "```\n",
    "```python\n",
    "Children = []\n",
    "for i in range(0, 6, 3):\n",
    "    Children.append(Child_triplet(i, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+1, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+2, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "```\n",
    "<mark>验证：</mark>\n",
    "```python\n",
    "len(Children[0].prefer_dict.keys())\n",
    "len(Children1[0][0])\n",
    "Children[0].prefer_dict[538]\n",
    "Children1[0][1][Children1[0][0].index(538)]\n",
    "Children1[0][2][Children1[0][0].index(538)]\n",
    "265\n",
    "265\n",
    "[384, -6]\n",
    "384\n",
    "-6\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:28:12.915402Z",
     "start_time": "2018-12-20T11:28:12.879022Z"
    }
   },
   "source": [
    "### 垃圾回收\n",
    "```python\n",
    "import gc\n",
    "Children = None\n",
    "Children1=None\n",
    "gc.collect()\n",
    "```python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 以下是我改写的存到Children1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:29:46.189593Z",
     "start_time": "2018-12-20T11:29:46.179287Z"
    }
   },
   "outputs": [],
   "source": [
    "#三胞胎\n",
    "def Triplet_Hij(Children,prefer1, prefer2, prefer3):\n",
    "    res=[[],[],[]]\n",
    "    for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):        \n",
    "        score = 0\n",
    "        #对于三胞胎中的第一个人，偏爱有各种礼物的得分\n",
    "        if p in list(prefer1):\n",
    "            score += 2*(100 - list(prefer1).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        #对于三胞胎中的第二个人\n",
    "        if p in list(prefer2):\n",
    "            score += 2*(100 - list(prefer2).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        #对于三胞胎中的第三个人\n",
    "        if p in list(prefer3):\n",
    "            score += 2*(100 - list(prefer3).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        res[0].append(p)\n",
    "        res[1].append(2*score)\n",
    "        res[2].append(-6)\n",
    "    Children.append(res)\n",
    "    Children.append(res)\n",
    "    Children.append(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:29:48.658270Z",
     "start_time": "2018-12-20T11:29:48.652165Z"
    }
   },
   "outputs": [],
   "source": [
    "#双胞胎\n",
    "def Twin_Hij(Children,prefer1, prefer2):\n",
    "    res=[[],[],[]]\n",
    "    for p in list(set(list(prefer1) + list(prefer2))):\n",
    "        score = 0\n",
    "        if p in list(prefer1):\n",
    "            score += 2*(100 - list(prefer1).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        if p in list(prefer2):\n",
    "            score += 2*(100 - list(prefer2).index(p))\n",
    "        else:\n",
    "            score -= 1\n",
    "        res[0].append(p)\n",
    "        res[1].append(3*score)\n",
    "        res[2].append(-6)\n",
    "    Children.append(res)\n",
    "    Children.append(res)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:29:51.587747Z",
     "start_time": "2018-12-20T11:29:51.581971Z"
    }
   },
   "outputs": [],
   "source": [
    "#普通孩子\n",
    "def Child_Hij(Children,prefer):\n",
    "    res=[[],[],[]]\n",
    "    for i in range(prefer.shape[0]):\n",
    "        score = 12*(prefer.shape[0] - i)\n",
    "        res[0].append(prefer[i])\n",
    "        res[1].append(score)\n",
    "        res[2].append(-6)\n",
    "    Children.append(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:33:22.302257Z",
     "start_time": "2018-12-20T11:29:53.065800Z"
    }
   },
   "outputs": [],
   "source": [
    "Children1=[]\n",
    "for i in range(0, 5001, 3):\n",
    "    Triplet_Hij(Children1,gift_pref[i], gift_pref[i+1], gift_pref[i+2])\n",
    "for j in range(5001, 45001, 2):\n",
    "    Twin_Hij(Children1,gift_pref[j], gift_pref[j+1])\n",
    "for k in range(45001, 1000000):\n",
    "    Child_Hij(Children1,gift_pref[k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:34:34.028658Z",
     "start_time": "2018-12-20T11:33:57.844236Z"
    }
   },
   "outputs": [],
   "source": [
    "#处理礼物偏爱的孩子\n",
    "for j in range(1000):\n",
    "    #每类礼物更偏爱的孩子\n",
    "    cf = child_pref[j]\n",
    "    done_list = []\n",
    "    for i in range(cf.shape[0]):\n",
    "        #同一礼物如果是三胞胎则以三胞胎中最先出现的为主。\n",
    "        if cf[i] <= 5000 and cf[i] not in done_list:\n",
    "            if cf[i] % 3 == 0:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                cid3 = cf[i] + 2\n",
    "                done_list.append(cid2)\n",
    "                done_list.append(cid3)\n",
    "            elif cf[i] % 3 == 1:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                cid3 = cf[i] + 1\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid3)\n",
    "            else:\n",
    "                cid1 = cf[i] - 2\n",
    "                cid2 = cf[i] - 1\n",
    "                cid3 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid2)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            if cid3 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid3))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            #判断孩子(cid1)是否偏爱礼物(j)\n",
    "            index_triplet_pref=index_of(Children1[cid1][0],j)\n",
    "            #存在修改\n",
    "            if index_triplet_pref>-1:\n",
    "                #修改Hji\n",
    "                Children1[cid1][2][index_triplet_pref]=2*score_                \n",
    "            else:\n",
    "                #要添加\n",
    "                Children1[cid1][0].append(j)\n",
    "                Children1[cid1][1].append(-6)\n",
    "                Children1[cid1][2].append(2*score_)\n",
    "            #判断孩子(cid1)是否偏爱礼物(j)\n",
    "            index_triplet_pref=index_of(Children1[cid2][0],j)\n",
    "            if index_triplet_pref>-1:\n",
    "                Children1[cid2][2][index_triplet_pref]=2*score_\n",
    "            else:\n",
    "                Children1[cid2][0].append(j)\n",
    "                Children1[cid2][1].append(-6)\n",
    "                Children1[cid2][2].append(2*score_)\n",
    "            index_triplet_pref=index_of(Children1[cid3][0],j)\n",
    "            #存在修改\n",
    "            if index_triplet_pref>-1:     \n",
    "                Children1[cid3][2][index_triplet_pref]=2*score_\n",
    "            else:\n",
    "                Children1[cid3][0].append(j)                \n",
    "                Children1[cid3][1].append(-6)                                \n",
    "                Children1[cid3][2].append(2*score_)         \n",
    "            #如果是双胞胎\n",
    "            #以双胞胎最先出现的为主\n",
    "        elif cf[i] <= 45000 and cf[i] not in done_list:\n",
    "            if cf[i] % 2 == 1:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                done_list.append(cid2)\n",
    "            else:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            #判断孩子(cid1)是否偏爱礼物(j)\n",
    "            index_twin_pref=index_of(Children1[cid1][0],j)\n",
    "            #存在修改\n",
    "            if index_twin_pref>-1:\n",
    "                Children1[cid1][2][index_twin_pref]=3*score_\n",
    "            else:\n",
    "                Children1[cid1][0].append(j)\n",
    "                Children1[cid1][1].append(-6)\n",
    "                Children1[cid1][2].append(3*score_)\n",
    "            #判断孩子(cid2)是否偏爱礼物(j)\n",
    "            index_twin_pref=index_of(Children1[cid2][0],j)\n",
    "            if index_twin_pref>-1:\n",
    "                Children1[cid2][2][index_twin_pref]=3*score_\n",
    "            else:\n",
    "                #注原来的代码只在双胞胎或三胞胎的第一个上面加了礼物索引\n",
    "                Children1[cid2][0].append(j)                \n",
    "                Children1[cid2][1].append(-6)                \n",
    "                Children1[cid2][2].append(3*score_)                                \n",
    "            #如果是普通孩子\n",
    "        elif cf[i] > 45000:\n",
    "            #判断孩子(cid1)是否偏爱礼物(j)\n",
    "            cid=cf[i]\n",
    "            score_=2*(cf.shape[0] - i)\n",
    "            index_child_pref=index_of(Children1[cid][0],j)\n",
    "            if index_child_pref>-1:\n",
    "                Children1[cid][2][index_child_pref]=6*score_\n",
    "            else:\n",
    "                Children1[cid][0].append(j)\n",
    "                Children1[cid][1].append(-6)\n",
    "                Children1[cid][2].append(6*score_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T06:46:18.213407Z",
     "start_time": "2018-12-20T06:46:18.209758Z"
    }
   },
   "source": [
    "### 原来的Children"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:36:22.855630Z",
     "start_time": "2018-12-20T11:36:22.846141Z"
    }
   },
   "outputs": [],
   "source": [
    "#非双胞胎和非三胞胎的孩子，因为成pair，因此-6只是占位符\n",
    "class Child(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        \n",
    "        for i in range(prefer.shape[0]):\n",
    "            self.prefer_dict[prefer[i]] = [12*(prefer.shape[0] - i), -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 6*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 6*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:36:25.113260Z",
     "start_time": "2018-12-20T11:36:25.103352Z"
    }
   },
   "outputs": [],
   "source": [
    "#双胞胎\n",
    "class Child_twin(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer1, prefer2):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        \n",
    "        for p in list(set(list(prefer1) + list(prefer2))):\n",
    "            score = 0\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            self.prefer_dict[p] = [3*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 3*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 3*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T11:36:28.687929Z",
     "start_time": "2018-12-20T11:36:28.677364Z"
    }
   },
   "outputs": [],
   "source": [
    "#三胞胎\n",
    "class Child_triplet(object):\n",
    "    \"\"\"对于三胞胎，三个人要作为整体考虑\n",
    "    param idx:child id \n",
    "    param prefer1:三胞胎中第一个孩子偏爱的礼物\n",
    "    param prefer2:三胞胎中第二个孩子偏爱的礼物\n",
    "    param prefer3:三胞胎中第三个孩子偏爱的礼物\n",
    "    \"\"\"\n",
    "    def __init__(self, idx, prefer1, prefer2, prefer3):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        #三胞胎三个人，有三组不同的喜欢的礼物，所以对于三胞胎set(list(prefer1) + list(prefer2) + list(prefer3))肯定大于100\n",
    "        for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):\n",
    "            score = 0\n",
    "            #对于三胞胎中的第一个人，偏爱有各种礼物的得分\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第二个人\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第三个人\n",
    "            if p in list(prefer3):\n",
    "                score += 2*(100 - list(prefer3).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #这个是在干啥？\n",
    "            self.prefer_dict[p] = [2*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        #最佳匹配\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 2*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 2*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T12:11:46.579705Z",
     "start_time": "2018-12-20T11:36:32.761997Z"
    }
   },
   "outputs": [],
   "source": [
    "Children = []\n",
    "for i in range(0, 5001, 3):\n",
    "    Children.append(Child_triplet(i, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+1, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+2, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "for i in range(5001, 45001, 2):\n",
    "    Children.append(Child_twin(i, gift_pref[i], gift_pref[i+1]))\n",
    "    Children.append(Child_twin(i+1, gift_pref[i], gift_pref[i+1]))\n",
    "Children = Children + [Child(i, gift_pref[i]) for i in range(45001, 1000000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T12:27:51.771190Z",
     "start_time": "2018-12-20T12:12:32.313818Z"
    }
   },
   "outputs": [],
   "source": [
    "for j in range(1000):\n",
    "    #每类礼物更偏爱的孩子\n",
    "    cf = child_pref[j]\n",
    "    done_list = []\n",
    "    for i in range(cf.shape[0]):\n",
    "        #同一礼物如果是三胞胎则以三胞胎中最先出现的为主。\n",
    "        if cf[i] <= 5000 and cf[i] not in done_list:\n",
    "            if cf[i] % 3 == 0:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                cid3 = cf[i] + 2\n",
    "                done_list.append(cid2)\n",
    "                done_list.append(cid3)\n",
    "            elif cf[i] % 3 == 1:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                cid3 = cf[i] + 1\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid3)\n",
    "            else:\n",
    "                cid1 = cf[i] - 2\n",
    "                cid2 = cf[i] - 1\n",
    "                cid3 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid2)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            if cid3 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid3))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            Children[cid3].add_gifts_prefer(j, score_)\n",
    "            #如果是双胞胎\n",
    "            #以双胞胎最先出现的为主\n",
    "        elif cf[i] <= 45000 and cf[i] not in done_list:\n",
    "            if cf[i] % 2 == 1:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                done_list.append(cid2)\n",
    "            else:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            #如果是普通孩子\n",
    "        elif cf[i] > 45000:\n",
    "            Children[cf[i]].add_gifts_prefer(j, 2*(cf.shape[0] - i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 校验是否正确"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T12:51:43.889278Z",
     "start_time": "2018-12-20T12:51:43.863913Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "270\n",
      "270\n",
      "121\n",
      "[388, -6]\n",
      "388\n",
      "-6\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "def validat_mychange(cid):\n",
    "    #判断giftid的数量是否相等\n",
    "    print(len(Children[cid].prefer_dict.keys()))\n",
    "    print(len(Children1[cid][0]))\n",
    "    #判断里面的值是否相等，随机取的一个\n",
    "    random_giftid=random.choice(Children1[cid][0])\n",
    "    print(random_giftid)\n",
    "    print(Children[cid].prefer_dict[random_giftid])\n",
    "    print(Children1[cid][1][Children1[cid][0].index(random_giftid)])\n",
    "    print(Children1[cid][2][Children1[cid][0].index(random_giftid)])\n",
    "#随机看一个child的情况\n",
    "validat_mychange(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-20T12:29:11.687067Z",
     "start_time": "2018-12-20T12:29:11.652454Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "268\n",
      "268\n",
      "95\n",
      "[76, -6]\n",
      "76\n",
      "-6\n"
     ]
    }
   ],
   "source": [
    "validat_mychange(4325)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 下面暂时没改，不过应该很容易改"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T11:06:19.797271Z",
     "start_time": "2018-12-18T11:06:18.512790Z"
    }
   },
   "outputs": [],
   "source": [
    "from ortools.graph import pywrapgraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T11:26:38.136254Z",
     "start_time": "2018-12-18T11:26:38.127840Z"
    }
   },
   "outputs": [],
   "source": [
    "W_CHILD = 10000\n",
    "W_GIFTS = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T11:27:46.657457Z",
     "start_time": "2018-12-18T11:27:46.649506Z"
    }
   },
   "outputs": [],
   "source": [
    "min_cost_flow_1 = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "# triplets\n",
    "for i in range(0, 5001, 3):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(3)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# triplets\n",
    "for i in range(5001, 45001, 2):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(2)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "\n",
    "# add Arc\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "for i in range(1000):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(1001001), int(1001000), int(1000000), int(0)\n",
    "    )\n",
    "\n",
    "\n",
    "# add Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(1000000+i), int(1000))\n",
    "\n",
    "# children\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow_1.SetNodeSupply(int(1001001), int(0)) \n",
    "min_cost_flow_1.SetNodeSupply(int(1001000), int(-1000000)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T13:35:32.667949Z",
     "start_time": "2018-12-13T13:35:32.661343Z"
    }
   },
   "source": [
    "#### 求最大公约数math.gcd\n",
    "```python\n",
    "greatest common divisor of x and y\n",
    "math.gcd(319,377)\n",
    "29\n",
    "```\n",
    "- 最大公约数=A×B/最小公倍数,下面的函数实际上是求的最小公倍数\n",
    "```python\n",
    "def lcm(a, b):\n",
    "    \"\"\"Compute the lowest common multiple of a and b\"\"\"\n",
    "    # in case of large numbers, using floor division\n",
    "    return a * b // math.gcd(a, b)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T13:42:45.142980Z",
     "start_time": "2018-12-13T13:42:45.137651Z"
    }
   },
   "outputs": [],
   "source": [
    "def lcm(a, b):\n",
    "    \"\"\"Compute the lowest common multiple of a and b，求的是最小公倍数\"\"\"\n",
    "    # in case of large numbers, using floor division\n",
    "    return a * b // math.gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def avg_normalized_happiness(pred, child_pref, gift_pref):\n",
    "    \n",
    "    # check if number of each gift exceeds n_gift_quantity\n",
    "    gift_counts = Counter(elem[1] for elem in pred)\n",
    "    for count in gift_counts.values():\n",
    "        assert count <= n_gift_quantity\n",
    "                \n",
    "    # check if triplets have the same gift\n",
    "    for t1 in np.arange(0,triplets,3):\n",
    "        triplet1 = pred[t1]\n",
    "        triplet2 = pred[t1+1]\n",
    "        triplet3 = pred[t1+2]\n",
    "        # print(t1, triplet1, triplet2, triplet3)\n",
    "        assert triplet1[1] == triplet1[1] and triplet2[1] == triplet3[1]\n",
    "                \n",
    "    # check if twins have the same gift\n",
    "    for t1 in np.arange(triplets,triplets+twins,2):\n",
    "        twin1 = pred[t1]\n",
    "        twin2 = pred[t1+1]\n",
    "        # print(t1)\n",
    "        assert twin1[1] == twin2[1]\n",
    "\n",
    "    max_child_happiness = n_gift_pref * ratio_child_happiness\n",
    "    max_gift_happiness = n_child_pref * ratio_gift_happiness\n",
    "    total_child_happiness = 0\n",
    "    total_gift_happiness = np.zeros(n_gift_type)\n",
    "    \n",
    "    for row in pred:\n",
    "        child_id = row[0]\n",
    "        gift_id = row[1]\n",
    "        \n",
    "        # check if child_id and gift_id exist\n",
    "        assert child_id < n_children\n",
    "        assert gift_id < n_gift_type\n",
    "        assert child_id >= 0 \n",
    "        assert gift_id >= 0\n",
    "        child_happiness = (n_gift_pref - np.where(gift_pref[child_id]==gift_id)[0]) * ratio_child_happiness\n",
    "        if not child_happiness:\n",
    "            child_happiness = -1\n",
    "\n",
    "        gift_happiness = ( n_child_pref - np.where(child_pref[gift_id]==child_id)[0]) * ratio_gift_happiness\n",
    "        if not gift_happiness:\n",
    "            gift_happiness = -1\n",
    "\n",
    "        total_child_happiness += child_happiness\n",
    "        total_gift_happiness[gift_id] += gift_happiness\n",
    "    \n",
    "    print('normalized child happiness=',float(total_child_happiness)/(float(n_children)*float(max_child_happiness)) , \\\n",
    "        ', normalized gift happiness',np.mean(total_gift_happiness) / float(max_gift_happiness*n_gift_quantity))\n",
    "\n",
    "    # to avoid float rounding error\n",
    "    # find common denominator\n",
    "    # NOTE: I used this code to experiment different parameters, so it was necessary to get the multiplier\n",
    "    # Note: You should hard-code the multipler to speed up, now that the parameters are finalized\n",
    "    denominator1 = n_children*max_child_happiness\n",
    "    denominator2 = n_gift_quantity*max_gift_happiness*n_gift_type\n",
    "    common_denom = lcm(denominator1, denominator2)\n",
    "    multiplier = common_denom / denominator1\n",
    "\n",
    "    # # usually denom1 > demon2\n",
    "    return float(math.pow(total_child_happiness*multiplier,3) + math.pow(np.sum(total_gift_happiness),3)) / float(math.pow(common_denom,3))\n",
    "    # return math.pow(float(total_child_happiness)/(float(n_children)*float(max_child_happiness)),2) + math.pow(np.mean(total_gift_happiness) / float(max_gift_happiness*n_gift_quantity),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from ortools.graph import pywrapgraph\n",
    "\n",
    "W_CHILD = 9020\n",
    "W_GIFTS = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_cost_flow_1 = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n",
    "\n",
    "\n",
    "# triplets\n",
    "for i in range(0, 5001, 3):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(3)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# triplets\n",
    "for i in range(5001, 45001, 2):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(2)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "\n",
    "# add Arc\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "for i in range(1000):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(1001001), int(1001000), int(1000000), int(0)\n",
    "    )\n",
    "\n",
    "\n",
    "# add Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(1000000+i), int(1000))\n",
    "\n",
    "# children\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow_1.SetNodeSupply(int(1001001), int(0)) \n",
    "min_cost_flow_1.SetNodeSupply(int(1001000), int(-1000000)) \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow_1.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9020 2 11739596220 1709307 1617929073662152820107354405443\n",
      "0.9363015472581903\n"
     ]
    }
   ],
   "source": [
    "assignment = [-1]*1000000\n",
    "twins_differ = []\n",
    "triplets_differ = []\n",
    "\n",
    "for i in range(min_cost_flow_1.NumArcs()):\n",
    "    if min_cost_flow_1.Flow(i) != 0 and min_cost_flow_1.Head(i) < 1000000:\n",
    "        c = min_cost_flow_1.Head(i)\n",
    "        g = min_cost_flow_1.Tail(i)\n",
    "        f = min_cost_flow_1.Flow(i)\n",
    "\n",
    "        if c >= 45001:\n",
    "            assignment[c] = g - 1000000\n",
    "\n",
    "        elif c >= 5001:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    twins_differ.append([c, c+1])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "            elif f == 2:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "        else:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                elif assignment[c+1] == -1:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                else:\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 2:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 3:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "                assignment[c+2] = g - 1000000\n",
    "                \n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(63, 2)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(twins_differ), len(triplets_differ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# well assigned twins and triplets\n",
    "well_assigned = []\n",
    "for i in range(0, 5001, 3):\n",
    "    if assignment[i] == assignment[i+1] and assignment[i] == assignment[i+2]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)\n",
    "        well_assigned.append(i+2)\n",
    "for i in range(5001, 45001, 2):\n",
    "    if assignment[i] == assignment[i+1]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44869"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(well_assigned)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Gifts_left = [1000 for _ in range(1000)]\n",
    "for i in well_assigned:\n",
    "    if assignment[i] != -1:\n",
    "        Gifts_left[assignment[i]] -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "958818"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(Gifts_left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# add penalty for twins and triplets\n",
    "W_CHILD = 90200000\n",
    "W_GIFTS = 20000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_cost_flow_2 = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n",
    "\n",
    "\n",
    "# triplets\n",
    "for i in range(0, 5001, 3):\n",
    "    if i not in well_assigned:\n",
    "        for g in Children[i].prefer_dict.keys():\n",
    "            start_nodes.append(1000000+g)\n",
    "            end_nodes.append(i)\n",
    "            capacities.append(3)\n",
    "            unit_costs.append(1-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "            \n",
    "# twins\n",
    "for i in range(5001, 45001, 2):\n",
    "    if i not in well_assigned:\n",
    "        for g in Children[i].prefer_dict.keys():\n",
    "            start_nodes.append(1000000+g)\n",
    "            end_nodes.append(i)\n",
    "            capacities.append(2)\n",
    "            unit_costs.append(1-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "\n",
    "# add Arc\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow_2.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_2.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_2.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_2.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "for i in range(1000):\n",
    "    min_cost_flow_2.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "min_cost_flow_2.AddArcWithCapacityAndUnitCost(\n",
    "        int(1001001), int(1001000), int(1000000), int(0)\n",
    "    )\n",
    "\n",
    "\n",
    "# add Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow_2.SetNodeSupply(int(1000000+i), int(Gifts_left[i]))\n",
    "\n",
    "# children\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_2.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_2.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_2.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow_2.SetNodeSupply(int(1001001), int(0)) \n",
    "min_cost_flow_2.SetNodeSupply(int(1001000), int(-sum(Gifts_left))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow_2.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assignment_0 = assignment.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "90200000 20000 11739596220 1709307 1617929073662152820107354405443\n",
      "0.9363015472581903\n"
     ]
    }
   ],
   "source": [
    "assignment = [-1]*1000000\n",
    "# pre-assigned\n",
    "for i in well_assigned:\n",
    "    assignment[i] = assignment_0[i]\n",
    "    \n",
    "twins_differ = []\n",
    "triplets_differ = []\n",
    "\n",
    "for i in range(min_cost_flow_2.NumArcs()):\n",
    "    if min_cost_flow_2.Flow(i) != 0 and min_cost_flow_2.Head(i) < 1000000:\n",
    "        c = min_cost_flow_2.Head(i)\n",
    "        g = min_cost_flow_2.Tail(i)\n",
    "        f = min_cost_flow_2.Flow(i)\n",
    "\n",
    "        if c >= 45001:\n",
    "            assignment[c] = g - 1000000\n",
    "\n",
    "        elif c >= 5001:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    twins_differ.append([c, c+1])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "            elif f == 2:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "        else:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                elif assignment[c+1] == -1:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                else:\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 2:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 3:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "                assignment[c+2] = g - 1000000\n",
    "                \n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(11, 2)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(twins_differ), len(triplets_differ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# well assigned twins and triplets\n",
    "well_assigned = []\n",
    "for i in range(0, 5001, 3):\n",
    "    if assignment[i] == assignment[i+1] and assignment[i] == assignment[i+2]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)\n",
    "        well_assigned.append(i+2)\n",
    "for i in range(5001, 45001, 2):\n",
    "    if assignment[i] == assignment[i+1]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Gifts_left = [1000 for _ in range(1000)]\n",
    "for i in well_assigned:\n",
    "    if assignment[i] != -1:\n",
    "        Gifts_left[assignment[i]] -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44973"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(well_assigned)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assignment_1 = assignment.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# add penalty for twins and triplets\n",
    "W_CHILD = 10000\n",
    "W_GIFTS = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "min_cost_flow_3 = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n",
    "\n",
    "np.random.seed(71)\n",
    "\n",
    "# triplets\n",
    "for i in range(0, 5001, 3):\n",
    "    if i not in well_assigned:\n",
    "        for g in Children[i].prefer_dict.keys():\n",
    "            start_nodes.append(1000000+g)\n",
    "            end_nodes.append(i)\n",
    "            capacities.append(3)\n",
    "            unit_costs.append(np.random.choice(100)-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "            \n",
    "# twins\n",
    "for i in range(5001, 45001, 2):\n",
    "    if i not in well_assigned:\n",
    "        for g in Children[i].prefer_dict.keys():\n",
    "            start_nodes.append(1000000+g)\n",
    "            end_nodes.append(i)\n",
    "            capacities.append(2)\n",
    "            unit_costs.append(np.random.choice(100)-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(np.random.choice(5)-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "\n",
    "# add Arc\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow_3.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_3.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_3.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_3.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "for i in range(1000):\n",
    "    min_cost_flow_3.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "min_cost_flow_3.AddArcWithCapacityAndUnitCost(\n",
    "        int(1001001), int(1001000), int(1000000), int(0)\n",
    "    )\n",
    "\n",
    "\n",
    "# add Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow_3.SetNodeSupply(int(1000000+i), int(Gifts_left[i]))\n",
    "\n",
    "# children\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_3.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_3.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_3.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow_3.SetNodeSupply(int(1001001), int(0)) \n",
    "min_cost_flow_3.SetNodeSupply(int(1001000), int(-sum(Gifts_left))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow_3.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 1 11739596220 1709307 1617929073662152820107354405443\n",
      "0.9363015472581903\n"
     ]
    }
   ],
   "source": [
    "assignment = [-1]*1000000\n",
    "# pre-assigned\n",
    "for i in well_assigned:\n",
    "    assignment[i] = assignment_1[i]\n",
    "    \n",
    "twins_differ = []\n",
    "triplets_differ = []\n",
    "\n",
    "for i in range(min_cost_flow_3.NumArcs()):\n",
    "    if min_cost_flow_3.Flow(i) != 0 and min_cost_flow_3.Head(i) < 1000000:\n",
    "        c = min_cost_flow_3.Head(i)\n",
    "        g = min_cost_flow_3.Tail(i)\n",
    "        f = min_cost_flow_3.Flow(i)\n",
    "\n",
    "        if c >= 45001:\n",
    "            assignment[c] = g - 1000000\n",
    "\n",
    "        elif c >= 5001:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    twins_differ.append([c, c+1])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "            elif f == 2:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "        else:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                elif assignment[c+1] == -1:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                else:\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 2:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 3:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "                assignment[c+2] = g - 1000000\n",
    "                \n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 0)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(twins_differ), len(triplets_differ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[34267, 34268]]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twins_differ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# well assigned twins and triplets\n",
    "well_assigned = []\n",
    "for i in range(0, 5001, 3):\n",
    "    if assignment[i] == assignment[i+1] and assignment[i] == assignment[i+2]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)\n",
    "        well_assigned.append(i+2)\n",
    "for i in range(5001, 45001, 2):\n",
    "    if assignment[i] == assignment[i+1]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(207, 494)"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "assignment[34267], assignment[34268]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assignment_2 = assignment.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# assign 207\n",
    "assignment[34267] = 207\n",
    "assignment[34268] = 207"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Gifts_left = [1000 for _ in range(1000)]\n",
    "for i in well_assigned:\n",
    "    if assignment[i] != -1:\n",
    "        Gifts_left[assignment[i]] -= 1\n",
    "Gifts_left[207] -= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# add penalty for twins and triplets\n",
    "W_CHILD = 10000\n",
    "W_GIFTS = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# without twins\n",
    "min_cost_flow_34267 = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n",
    "      \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "\n",
    "# add Arc\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow_34267.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_34267.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "for i in range(1000):\n",
    "    min_cost_flow_34267.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "min_cost_flow_34267.AddArcWithCapacityAndUnitCost(\n",
    "    int(1001001), int(1001000), int(1000000), int(0)\n",
    ")\n",
    "\n",
    "\n",
    "# children\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_34267.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow_34267.SetNodeSupply(int(1001001), int(0))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# add Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow_34267.SetNodeSupply(int(1000000+i), int(Gifts_left[i]))\n",
    "    \n",
    "min_cost_flow_34267.SetNodeSupply(int(1001000), int(-sum(Gifts_left)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow_34267.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 1 11739596220 1703388 1617929073662101118387373555072\n",
      "0.9363015472581604\n"
     ]
    }
   ],
   "source": [
    "assignment = [-1]*1000000\n",
    "# pre-assigned\n",
    "for i in well_assigned:\n",
    "    assignment[i] = assignment_2[i]\n",
    "\n",
    "assignment[34267] = 207\n",
    "assignment[34268] = 207\n",
    "\n",
    "for i in range(min_cost_flow_34267.NumArcs()):\n",
    "    if min_cost_flow_34267.Flow(i) != 0 and min_cost_flow_34267.Head(i) < 1000000:\n",
    "        c = min_cost_flow_34267.Head(i)\n",
    "        g = min_cost_flow_34267.Tail(i)\n",
    "\n",
    "        assignment[c] = g - 1000000\n",
    "\n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([2742, 950, 0], [914, 475])"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unassigned_v = [0, 0, 0]\n",
    "unassigned_v_ = [0, 0]\n",
    "for i in range(5001):\n",
    "    if assignment[i] == -1:\n",
    "        unassigned_v[0] += 1\n",
    "for i in range(5001, 45001):\n",
    "    if assignment[i] == -1:\n",
    "        unassigned_v[1] += 1\n",
    "for i in range(45001, 1000000):\n",
    "    if assignment[i] == -1:\n",
    "        unassigned_v[2] += 1 \n",
    "for i in range(0, 5001, 3):\n",
    "    if assignment[i] == -1:\n",
    "        unassigned_v_[0] += 1\n",
    "for i in range(5001, 45001, 2):\n",
    "    if assignment[i] == -1:\n",
    "        unassigned_v_[1] += 1\n",
    "unassigned_v, unassigned_v_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "118 628\n",
      "240 180\n",
      "272 141\n",
      "320 496\n",
      "389 148\n",
      "494 983\n",
      "671 707\n",
      "998 409\n"
     ]
    }
   ],
   "source": [
    "Gifts_left = [1000 for _ in range(1000)]\n",
    "for i in range(1000000):\n",
    "    if assignment[i] != -1:\n",
    "        Gifts_left[assignment[i]] -= 1\n",
    "for i in range(1000):\n",
    "    if Gifts_left[i] != 0:\n",
    "        print(i, Gifts_left[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gifts_for_trips = [628, 180, 141, 496, 148, 983, 707, 409]\n",
    "gifts_for_twins = [4, 0, 0, 4, 4, 932, 2, 4]\n",
    "for i in range(8):\n",
    "    gifts_for_trips[i] -= gifts_for_twins[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gifts_left_list = []\n",
    "for i in range(gifts_for_trips[0]):\n",
    "    gifts_left_list.append(118)\n",
    "for i in range(gifts_for_trips[1]):\n",
    "    gifts_left_list.append(240)\n",
    "for i in range(gifts_for_trips[2]):\n",
    "    gifts_left_list.append(272)\n",
    "for i in range(gifts_for_trips[3]):\n",
    "    gifts_left_list.append(320)\n",
    "for i in range(gifts_for_trips[4]):\n",
    "    gifts_left_list.append(389)\n",
    "for i in range(gifts_for_trips[5]):\n",
    "    gifts_left_list.append(494)\n",
    "for i in range(gifts_for_trips[6]):\n",
    "    gifts_left_list.append(671)\n",
    "for i in range(gifts_for_trips[7]):\n",
    "    gifts_left_list.append(998)\n",
    "    \n",
    "for i in range(gifts_for_twins[0]):\n",
    "    gifts_left_list.append(118)\n",
    "for i in range(gifts_for_twins[1]):\n",
    "    gifts_left_list.append(240)\n",
    "for i in range(gifts_for_twins[2]):\n",
    "    gifts_left_list.append(272)\n",
    "for i in range(gifts_for_twins[3]):\n",
    "    gifts_left_list.append(320)\n",
    "for i in range(gifts_for_twins[4]):\n",
    "    gifts_left_list.append(389)\n",
    "for i in range(gifts_for_twins[5]):\n",
    "    gifts_left_list.append(494)\n",
    "for i in range(gifts_for_twins[6]):\n",
    "    gifts_left_list.append(671)\n",
    "for i in range(gifts_for_twins[7]):\n",
    "    gifts_left_list.append(998)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assignment_3 = assignment.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ind = 0\n",
    "for i in range(1000000):\n",
    "    if assignment[i] == -1:\n",
    "        assignment[i] = gifts_left_list[ind]\n",
    "        ind += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "out = open('../submit/seed71_solution.csv', 'w')\n",
    "out.write('ChildId,GiftId\\n')\n",
    "for i in range(1000000):\n",
    "    out.write(str(i) + ',' + str(assignment[i]) + '\\n')\n",
    "out.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
